/*************************************************************************
 * File Name:    Word_Break.cc
 * Author:       zero91
 * Mail:         jianzhang9102@gmail.com
 * Created Time: 2013/10/26 10:21:13
 * 
 * Description:  
 *
 |-------------------------------------------------------------------------
 | Prblem: Word Break
 |
 | Given a string s and a dictionary of words dict, determine if s can be
 | segmented into a space-separated sequence of one or more dictionary words.
 |
 | For example, given
 | s = "leetcode",
 | dict = ["leet", "code"].
 |
 | Return true because "leetcode" can be segmented as "leet code".
 |-------------------------------------------------------------------------
 * 
 ************************************************************************/

#include <iostream>
#include <fstream>
#include <sstream>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <deque>
#include <map>
#include <set>
#include <functional>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cmath>

using namespace std;

class Solution_1 {
public:
    bool wordBreak(string s, unordered_set<string> &dict) {
        typedef unordered_set<string>::iterator dict_iter_t;
        
        bool dp[s.size() + 1];
        
        memset(dp, false, sizeof(dp));
        dp[0] = true;
        bool flag = true;
        while (flag) {
            flag = false;
            for (dict_iter_t it = dict.begin(); it != dict.end(); ++it) {
                for (size_t i = 0; i + it->size() <= s.size(); ++i) {
                    if (dp[i] && s.substr(i, it->size()) == *it) {
                        if (!dp[i + it->size()]) {
                            dp[i + it->size()] = true;g
                            flag = true;
                        }
                    }
                }
            }
        }
        return dp[s.size()];
    }
};

class Solution_2 {
public:
    bool wordBreak(string s, unordered_set<string> &dict) {
        vector<bool> dp(s.size() + 1, false);
        dp[0] = true;
        
        for (size_t i = 1; i <= s.size(); ++i) {
            for (size_t j = 0; j < i; ++j) {
                if (dp[j] && dict.find(s.substr(j, i - j)) != dict.end()) {
                    dp[i] = true;
                }
            }
        }
        return dp[s.size()];
    }
};

class Solution {
public:
    bool wordBreak(string s, unordered_set<string> &dict) {
        typedef unordered_set<string>::iterator dict_iter_t;
        
        vector<bool> dp(s.size() + 1, false);
        dp[0] = true;
        
        for (size_t i = 0; i <= s.size(); ++i) {
            if (!dp[i]) continue;
            for (dict_iter_t it = dict.begin(); it != dict.end(); ++it) {
                if (i + it->size() <= s.size() && s.substr(i, it->size()) == *it) {
                    dp[i + it->size()] = true;
                }
            }
        }
        return dp[s.size()];
    }
};

